package com.jzoffer;

public class SubTree {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);

        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t3.left = t5;
        t5.right = t6;

        TreeNode t51 = new TreeNode(5);
        TreeNode t61 = new TreeNode(6);

        t51.right = t61;

        System.out.println(HasSubtree(t1,t51));

    }

    public static boolean HasSubtree(TreeNode root1,TreeNode root2){
        if(root1 == null || root2 == null){
            return false;
        }
        boolean flag = false;
        if(root1.val == root2.val){
            flag = isSubtree(root1,root2);
        }
        if(!flag){
            flag = HasSubtree(root1.left,root2);
        }
        if(!flag){
            flag = HasSubtree(root1.right,root2);
        }
        return flag;
    }

    private static boolean isSubtree(TreeNode root1,TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }
        if(root1.val == root2.val){
            return isSubtree(root1.left,root2.left) && isSubtree(root1.right,root2.right);
        }else{
            return false;
        }
    }

}
